package main

import (
	"fmt"
	"oslab/model"
	"sort"
)

const (
	Free = 0
	Used = 1
)

// cycleFirstAcclimation 循环首次适应算法
func cycleFirstAcclimation(space []*model.Space, works []*model.Work) {
	// 存有已持有的，名字、指向连续内存空间的开始地址
	dir := make(map[string]*model.Space, 0)
	// remember the last offer space index
	index := -1
	for i := 0; i < len(works); i++ {
		j := 0
		if works[i].Operate == model.Offer {
			// get the first fix one
			if index >= len(space)-1 {
				j = 0
			} else {
				j = index + 1
			}
			for ; j < len(space); j++ {
				if j == index {
					panic("out of memory")
				}
				if space[j].FreeSpace >= works[i].Space && space[j].Status == Free {
					space[j].FreeSpace -= works[i].Space
					if space[j].FreeSpace == 0 {
						// 说明所有都被分配了
						copy(space[:j], space[j+1:])
					}
					insert := model.NewSpace(works[i].Space, Used)
					// 将分片的空间插入, 这里是将j后的都后移一位, 在j的位置将该空间插入
					space = append(space, insert)
					copy(space[j+1:], space[j:])
					space[j] = insert
					index = j
					dir[works[i].Name] = space[j]
					print(space)
					break
				}
				if j == len(space)-1 {
					j = 0
				}
			}
		} else if works[i].Operate == model.Release {
			// 回收空间
			now := dir[works[i].Name]
			now.Status = Free
			delete(dir, works[i].Name)
			// 释放的空闲空间向左右的空闲空间自动合并
			// 此处可以用双链表的数据结构来优化
			for c := 0; c < len(space); c++ {
				if space[c] == now {
					if c > 0 && space[c-1].Status == Free {
						space[c-1].FreeSpace += now.FreeSpace
						copy(space[c:], space[c+1:])
						space = space[:len(space)-1]
						c--
					}
					if c < len(space)-1 && space[c+1].Status == Free {
						space[c+1].FreeSpace += now.FreeSpace
						copy(space[c:], space[c+1:])
						space = space[:len(space)-1]
					}
					break
				}
			}
			print(space)
		}

	}
}

func print(list []*model.Space) {
	fmt.Println()
	for i := range list {
		fmt.Println(list[i])
	}
	fmt.Println()
}

func printFree(list []*model.FreeSpace) {
	fmt.Println()
	for i := range list {
		fmt.Println(list[i].Index)
	}
	fmt.Println("---------------------")
}

// bestFitAlgorithm 最佳适应算法
// 优先使用小空间
func bestFitAlgorithm(space []*model.Space, works []*model.Work) {
	// 存有已持有的，名字、指向连续内存空间的开始地址
	dir := make(map[string]*model.Space, 0)
	// 维护的单调空闲空间队列
	minFreeSpace := make([]*model.FreeSpace, 0, len(space))
	// init
	for i := 0; i < len(space); i++ {
		minFreeSpace = append(minFreeSpace, model.NewFreeSpace(space[i].FreeSpace, space[i]))
	}
	sort.Slice(minFreeSpace, func(i, j int) bool {
		return minFreeSpace[i].Index.FreeSpace < minFreeSpace[j].Index.FreeSpace
	})

	for i := 0; i < len(works); i++ {
		if works[i].Operate == model.Offer {
			for j := 0; j < len(minFreeSpace); j++ {
				// 查找到适应的空闲空间
				if minFreeSpace[j].FreeSpace >= works[i].Space {
					// offer
					minFreeSpace[j].Index.FreeSpace -= works[i].Space
					minFreeSpace[j].FreeSpace -= works[i].Space
					// get index, 使用双链表可以优化
					c, flag := 0, true
					for c = 0; c < len(space); c++ {
						if space[c] == minFreeSpace[j].Index {
							break
						}
					}
					// change space
					if minFreeSpace[j].Index.FreeSpace == 0 {
						copy(space[c:], space[c+1:])
						space = space[:len(space)-1]
						copy(minFreeSpace[j:], minFreeSpace[:j+1])
						minFreeSpace = minFreeSpace[:len(minFreeSpace)-1]
						flag = false
					}

					// new one space and insert to space
					insert := model.NewSpace(works[i].Space, Used)
					// 将分片的空间插入, 这里是将j后的都后移一位, 在j的位置将该空间插入
					space = append(space, insert)
					copy(space[c+1:], space[c:])
					space[c] = insert
					dir[works[i].Name] = insert

					if flag {
						sort.Slice(minFreeSpace, func(i, j int) bool {
							return minFreeSpace[i].Index.FreeSpace < minFreeSpace[j].Index.FreeSpace
						})
					}
					print(space)
					printFree(minFreeSpace)

					break
				}
			}
		} else if works[i].Operate == model.Release {
			// Release and set free space
			// 回收空间
			now := dir[works[i].Name]
			now.Status = Free
			delete(dir, works[i].Name)
			index := 0
			// 释放的空闲空间向左右的空闲空间自动合并
			// 此处可以用双链表的数据结构来优化
			for c := 0; c < len(space); c++ {
				if space[c] == now {
					if c > 0 && space[c-1].Status == Free {
						for b := 0; b < len(minFreeSpace); b++ {
							if minFreeSpace[b].Index == space[c-1] {
								copy(minFreeSpace[b:], minFreeSpace[b+1:])
								minFreeSpace = minFreeSpace[:len(minFreeSpace)-1]
							}
						}
						space[c-1].FreeSpace += now.FreeSpace
						copy(space[c:], space[c+1:])
						space = space[:len(space)-1]
						c--
					}
					if c < len(space)-1 && space[c+1].Status == Free {
						for b := 0; b < len(minFreeSpace); b++ {
							if minFreeSpace[b].Index == space[c+1] {
								copy(minFreeSpace[b:], minFreeSpace[b+1:])
								minFreeSpace = minFreeSpace[:len(minFreeSpace)-1]
							}
						}
						space[c+1].FreeSpace += now.FreeSpace
						copy(space[c:], space[c+1:])
						space = space[:len(space)-1]
					}
					index = c
					break
				}
			}
			// Done: 这个地方要注意已有的freeSpace被合并了，那么他们的minFreeSpace也要做出改变

			minFreeSpace = append(minFreeSpace, model.NewFreeSpace(space[index].FreeSpace, space[index]))
			sort.Slice(minFreeSpace, func(i, j int) bool {
				return minFreeSpace[i].Index.FreeSpace < minFreeSpace[j].Index.FreeSpace
			})
			print(space)
			printFree(minFreeSpace)
		}
	}

}
